Exercises for A* Algorithm for 3×3 Puzzle

<div id='tr0-output'></div> <!-- library that includes functions and Queue --> <script src='http://cs.tru.ca/~mlee/comp3710/Software/board_game.js'></script> <!-- ulitity functions that you ca use --> <script> /* * Utility functions - you do not have to complete anything here. */ function print_message(m) { document.getElementById('output').innerHTML += m + '<br>'; } function get_id_of_board(board) { return board.join(','); } function get_id_of_node(node) { return node.id; } function get_board_of_node(node) { return node.board; } function get_gvalue_of_node(node) { return node.gvalue; } function get_hvalue_of_node(node) { return node.hvalue; } function get_fvalue_of_node(node) { return node.fvalue; } function get_parent_node_of_node(node) { return node.parent; } function switch_two_tiles_in_board(board, i, j) { var tmp; tmp = board[i]; board[i] = board[j]; board[j] = tmp; } function copy_board(board_from, board_to) { var i; for (i = 0; i < board_from.length; i++) board_to[i] = board_from[i]; } function factorial(x) { if (x == 0) return 1; return x * factorial(x-1); } function get_next_boards(board, board_0, board_1, board_2, board_3) { if (index_of_empty_cell(board) == 0) { copy_board(board, board_0); copy_board(board, board_1); switch_two_tiles_in_board(board_0, 0, 1); switch_two_tiles_in_board(board_1, 0, SIZE); } else if (index_of_empty_cell(board) == 1) { copy_board(board, board_0); copy_board(board, board_1); copy_board(board, board_2); switch_two_tiles_in_board(board_0, 1, 1-1); switch_two_tiles_in_board(board_1, 1, 1+1); switch_two_tiles_in_board(board_2, 1, 1+SIZE); } else if (index_of_empty_cell(board) == 2) { copy_board(board, board_0); copy_board(board, board_1); switch_two_tiles_in_board(board_0, 2, 2-1); switch_two_tiles_in_board(board_1, 2, 2+SIZE); } else if (index_of_empty_cell(board) == 3) { copy_board(board, board_0); copy_board(board, board_1); copy_board(board, board_2); switch_two_tiles_in_board(board_0, 3, 3-SIZE); switch_two_tiles_in_board(board_1, 3, 3+1); switch_two_tiles_in_board(board_2, 3, 3+SIZE); } else if (index_of_empty_cell(board) == 4) { copy_board(board, board_0); copy_board(board, board_1); copy_board(board, board_2); copy_board(board, board_3); switch_two_tiles_in_board(board_0, 4, 4-SIZE); switch_two_tiles_in_board(board_1, 4, 4-1); switch_two_tiles_in_board(board_2, 4, 4+1); switch_two_tiles_in_board(board_3, 4, 4+SIZE); } else if (index_of_empty_cell(board) == 5) { copy_board(board, board_0); copy_board(board, board_1); copy_board(board, board_2); switch_two_tiles_in_board(board_0, 5, 5-SIZE); switch_two_tiles_in_board(board_1, 5, 5-1); switch_two_tiles_in_board(board_2, 5, 5+SIZE); } else if (index_of_empty_cell(board) == 6) { copy_board(board, board_0); copy_board(board, board_1); switch_two_tiles_in_board(board_0, 6, 6+1); switch_two_tiles_in_board(board_1, 6, 6-SIZE); } else if (index_of_empty_cell(board) == 7) { copy_board(board, board_0); copy_board(board, board_1); copy_board(board, board_2); switch_two_tiles_in_board(board_0, 7, 7-SIZE); switch_two_tiles_in_board(board_1, 7, 7-1); switch_two_tiles_in_board(board_2, 7, 7+1); } else if (index_of_empty_cell(board) == 8) { copy_board(board, board_0); copy_board(board, board_1); switch_two_tiles_in_board(board_0, 8, 8-1); switch_two_tiles_in_board(board_1, 8, 8-SIZE); } } $('#tr0-output').html("All utility functions are loaded."); </script> Submit and execute the code

<div id='tr1-output'></div> <script> function is_the_goal_board(board) // The goal board is [1, 2, 3, ..., 8, 0] { var length = board.length; for (var i = 0; i < length-1; i++) // Except the last tile ??? return true; } var board0 = [0, 8, 7, 3, 5, 1, 4, 6, 2]; var board1 = [1, 2, 3, 4, 5, 6, 7, 8, 0]; var tmp0 = is_the_goal_board(board0); var tmp1 = is_the_goal_board(board1); $('#tr1-output').html(tmp0 + ", " + tmp1); </script> Execute the code

<div id='tr2-output'></div> <script> function get_heuristic_value(board) { var count = 0; for (var i = 0; i < board.length; i++) ??? // goal board = [1, 2, 3, 4, 5, 6, 7, 8, 0], where 0 is empty tile. return count; } var board = [0, 8, 7, 3, 5, 1, 4, 6, 2]; var h_value = get_heuristic_value(board); $('#tr2-output').html(h_value); </script> Execute the code

<div id='tr3-output'></div> <script> function create_node(board, gvalue, parent_node) { var node = { id: get_id_of_board(board), board: board, gvalue: gvalue, hvalue: ???(board), // get_heuristic_value() should be implemented fvalue: ???, parent: ??? // to keep the track of path from the initial board to the goal board }; return node; } var parent_board = [0, 8, 7, 3, 5, 1, 4, 6, 2]; var neighbor_board = [8, 0, 7, 3, 5, 1, 4, 6, 2]; var parent_node = create_node(parent_board, 0, null); var node = create_node(neighbor_board, 0 + 1, parent_node); $('#tr3-output').html(get_fvalue_of_node(node)); </script> Execute the code

<div id='tr4-output'></div> <script> function push_or_update_node_in_expandedQ(node) { // If the node is already in the expanded queue, then update g-value if (???.???(get_id_of_node(node))) { var node_old = expandedQ.get(get_id_of_node(node)); if (get_gvalue_of_node(node) ??? get_gvalue_of_node(node_old)) { // if ..., the replace it with the current node. expandedQ.pop(get_id_of_node(node)); expandedQ.???(???); } } // Otherwise, push the node into the expandedQ else ??? } var expandedQ = new Queue(); var parent_board = [0, 8, 7, 3, 5, 1, 4, 6, 2]; var neighbor_board0 = [8, 0, 7, 3, 5, 1, 4, 6, 2]; var neighbor_board1 = [3, 8, 7, 0, 5, 1, 4, 6, 2]; var parent_node = create_node(parent_board, 0, null); var node0 = create_node(neighbor_board0, 0 + 1, parent_node); var node1 = ???(neighbor_board1, 0 + 1, parent_node); push_or_update_node_in_expandedQ(parent_node); push_or_update_node_in_expandedQ(node0); push_or_update_node_in_expandedQ(node1); var tmp_node0 = expandedQ.popTheHighestPriorityOne(); $('#tr4-output').html(get_board_of_node(tmp_node0)); </script> Execute the code